package cn.dapeng.utils;

import cn.dapeng.tree.binary.TreeNode;

import java.util.Stack;

/**
 * @BelongProject study
 * @BelongPackage cn.dapeng.tree.binary
 * @Description TODO
 * @ClassName BinaryTreeCreator
 * @Author xupenghong
 * @Date 2024/8/20 11:45
 * @Version 1.0.0
 */
public class BinaryTreeCreator {

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(0);

        TreeNode l = new TreeNode(1);
        TreeNode r = new TreeNode(2);

        treeNode.left = l;
        treeNode.right = r;

        TreeNode r1 = new TreeNode(3);
        r.right = r1;

        TreeNode rl = new TreeNode(4);
        l.right = rl;

        in_recursion(treeNode);
        System.out.println();
        in(treeNode);
    }

    /**
     * 先序遍历:递归方式  头->左->右
     * @param treeNode
     */
    public static void pre_recursion(TreeNode treeNode) {
        if (treeNode == null) {
            return;
        }
        System.out.print(treeNode.val + " ");
        pre_recursion(treeNode.left);
        pre_recursion(treeNode.right);
    }

    /**
     * 先序遍历非递归方式
     * <p>
     * 1.使用栈的方式实现
     * 2.先把头节点压入栈中，然后弹出，有右节点先添加右节点，然后在添加左节点
     * 3.弹出栈顶元素，重复操作：有右节点先添加右节点，然后在添加左节点
     *
     * @param treeNode
     */
    public static void pre(TreeNode treeNode) {
        if (treeNode == null) {
            return;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.push(treeNode);

        while (!stack.isEmpty()) {
            TreeNode x = stack.pop();
            System.out.print(x.val + " ");
            if (x.right != null) {
                stack.push(x.right);
            }
            if (x.left != null) {
                stack.push(x.left);
            }
        }
        System.out.println();
    }

    /**
     * 中序遍历:递归方式 左 → 头 → 右
     * @param treeNode
     */
    public static void in_recursion(TreeNode treeNode) {
        if(treeNode == null) {
            return;
        }
        in_recursion(treeNode.left);
        System.out.print(treeNode.val + " ");
        in_recursion(treeNode.right);
    }


    /**
     * 1 当前节点，整条左边界的节点全部入栈，直到空节点
     * 2 从栈中弹出节点打印， 把当前节点的右节点入栈，重复第一步
     *
     * @param currenNoe
     */
    public static void in(TreeNode currenNoe) {
        if (currenNoe == null) {
            return;
        }

        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || currenNoe != null) {
            if (currenNoe != null) {
                stack.push(currenNoe);
                currenNoe = currenNoe.left;
            } else {
                currenNoe = stack.pop();
                System.out.print(currenNoe.val + " ");
                currenNoe = currenNoe.right;
            }
        }
        System.out.println();
    }

    /**
     * 中序遍历:递归方式 左 → 右 → 头
     * @param treeNode
     */
    public static void pos_recursion(TreeNode treeNode) {
        if (treeNode == null) {
            return;
        }
        pos_recursion(treeNode.left);
        pos_recursion(treeNode.right);
        System.out.print(treeNode.val + " ");
    }

    /**
     * 使用两个栈实现后续遍历
     *
     * @param treeNode
     */
    public static void pos(TreeNode treeNode) {
        if (treeNode == null) {
            return;
        }

        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        stack1.push(treeNode);
        while (!stack1.isEmpty()) {
            treeNode = stack1.pop(); // 头右左 逆序 就是左右头  后续
            stack2.push(treeNode);

            if (treeNode.left != null) {
                stack1.push(treeNode.left);
            }
            if (treeNode.right != null) {
                stack1.push(treeNode.right);
            }
        }

        while (!stack2.isEmpty()) {
            System.out.print(stack2.pop().val + " ");
        }
        System.out.println();
    }


    public static TreeNode buildTreeNode(int maxLevel, int maxValue) {
        return generate(0, maxLevel, maxValue);
    }

    public static TreeNode generate(int level, int maxLevel, int maxValue) {
        if (level > maxLevel || Math.random() < 0.5) {
            return null;
        }

        TreeNode head = new TreeNode((int) (Math.random() * maxValue));
        head.left = generate(level + 1, maxLevel, maxValue);
        head.right = generate(level + 1, maxLevel, maxValue);
        return head;
    }

}
